import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        int[] A = new int[]{5,3,6,1,3};
        int k =2;
        int res = solution(A,k);
        System.out.println(res);
    }

    public static int solution(int[] A, int k){
        TreeMap<Integer, Integer> map = new TreeMap<>();
        //从索引为k的数开始遍历数组，将后面的数出现的次数存入一个TreeMap
        //TreeMap本质还是一个Map，只是会按照key的大小升序排列键值对
        for (int i = k; i < A.length; i++) {
            if (map.containsKey(A[i])) {
                int n = map.get(A[i]);
                map.put(A[i], n + 1);
            } else {
                map.put(A[i], 1);
            }
        }
        int min = map.lastKey() - map.firstKey();
        for (int i = k; i < A.length; i++) {
            //i指向k，相当于第一个窗口已经走过了，此时指向的是第二个窗口的尾部元素
            //将元素出现次数-1，相当于移除窗口内元素，减到1时删除，说明全部出现完毕
            int n = map.get(A[i]);
            if (n == 1) map.remove(A[i]);
            else map.put(A[i], n - 1);
            //A[i-k]是当前窗口头部的前一个元素，因为窗口右移的过程就相当于是在移除窗口内连续的k个元素，那么窗口前面的元素就要重新回到数组里，则将其出现次数+1
            if (map.containsKey(A[i - k])) {
                int x = map.get(A[i - k]);
                map.put(A[i - k], x + 1);
            } else {
                map.put(A[i - k], 1);
            }
            //Map不断排序，则不断更新差值
            min = Math.min(map.lastKey() - map.firstKey(), min);
        }
        return min;
    }
}
